#define CI( _x ) scanf("%d", &(_x) )
#define CL( _x ) scanf( "%lld", &(_x) )
#define CS( _x ) cin>>(_x)
#define fo(i,ed) for(int i = 0 ; i < ed ; ++i )
#define foit(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
#define bip system("pause")
#define Int long long
#define pb push_back
#define SZ(X) (int)(X).size()
#define LN(X) (int)(X).length()
#define mk make_pair
#define f first
#define s second
#define SET( ARRAY , VALUE ) memset( ARRAY , VALUE , sizeof(ARRAY) )

template< class T >
    inline T two ( T var ) {
    return var*var ;
}

inline void wait ( double seconds ) {
    double endtime = clock() + ( seconds* CLOCKS_PER_SEC );
    while ( clock() < endtime ) {
        ;
    }
}
template<class T1, class T2>
        inline T1 fastPow ( T1 x, T2 y ) {
        T1 res= ( T1 ) 1;
        for ( ; y ; ) {
            if ( ( y&1 ) ) {
                res*= x;
            }
            x*=x;
            y>>=1;
        }
        return res;
    }
template< class T >
    inline void read_array ( vector< T > &_array, int _size ) {
    _array.assign ( _size, T() );
    fo ( i,_size ) {
        CI ( _array[i] );
        //CL(_array[i]);
        //CS( _array[i] );

    }
}
template< class T1, class T2 >
        inline T2 MOD ( T1 x , T2 b ) {
        return ( x%b );
    }
template< class T >
    inline T gcd ( T a, T b ) {
    // NEGATIVE VALUE'R GCD HOTE PARBE NA
    assert ( ( a >=0 && b>=0 ) );
    while ( b > T ( 0 ) ) {
        a%=b;
        swap ( a,b );
    }
    return a;
}

inline int toI ( string _str ) {
    // STRING EMPTY HOTE PARBE NA
    assert ( LN ( _str ) );
    int var;
    sscanf ( _str.c_str(),"%d",&var );
    return var;
}
inline string toS ( int var ) {
    char _buff[50];
    sprintf ( _buff,"%d",var );
    return ( string ) _buff;
}

inline vector<int> find_lis ( vector<int> &a ) {
    vector< int > lis ( SZ ( a ),0 );
    vector< int > b ( SZ ( a ) );
    int maxLen = 1, lowBound;
    lis[0]=1,b[0]=a[0];

    for ( int i = 1; i < SZ ( a ); ++i ) {
        lowBound = lower_bound ( b.begin(),b.begin() +maxLen, a[i] )-b.begin();
        lis[i]=lowBound+1;
        if ( lowBound == maxLen ) {
            b[ maxLen ] = a[i];
            ++maxLen;
        } else {
            b[ lowBound ] = a[i];
        }
    }
    return lis;
}
inline void find_lis ( vector<int> &a, vector<int> &b ) {
    vector<int> p ( SZ ( a ) );
    int n = SZ ( a );
    int u,v;

    if ( n < 1 ) return ;
    b.push_back ( ( int ) 0 );

    for ( int i=1; i<n; ++i ) {
        if ( a[ b.back() ] < a[i] ) {
            p[i] = b.back();
            b.push_back ( i );
            continue;
        }
        for ( u=0,v=SZ ( b )-1; u < v ; ) {
            int c = ( u+v ) /2;
            if ( a[ b[c] ] < a[i] ) {
                u = c+1;
            } else {
                v = c;
            }
        }
        if ( a[i] < a[ b[u] ] ) {
            if ( u > 0 ) {
                p[i]=b[u-1];
            }
            b[u]=i;
        }
    }

    for ( u=SZ ( b ),v=b.back(); u--; v=p[v] ) {
        b[u]=v;
    }
}

template<class T1, class T2>
        inline T1 OR ( T1 msk,T2 bit ) {
        return ( msk| ( 1LL<<bit ) );
    }
template<class T1, class T2>
        inline T1 AND ( T1 msk, T2 bit ) {
        return ( msk& ( 1LL<<bit ) );
    }
template<class T1, class T2>
        inline T1 XOR ( T1 msk, T2 bit ) {
        return ( msk& ( ~ ( 1LL<<bit ) ) );
    }
template<class T1, class T2>
        inline bool marked ( T1 msk, T2 bit ) {
        return ( AND ( msk,bit ) !=0 );
    }


#define line puts("")
template<class T>
    inline void debug ( T _x ) {
    cout<<_x<<'\n';
}
template<class T1, class T2>
        inline void debug ( T1 _x,T2 _y ) {
        cout<<_x<<' '<<_y<<'\n';
    }
template<class T1, class T2, class T3>
            inline void debug ( T1 _x,T2 _y,T3 _z ) {
            cout<<_x<<' '<<_y<<' '<<_z<<'\n';
        }
template<class T1, class T2, class T3, class T4>
                inline void debug ( T1 _x,T2 _y,T3 _z,T4 _zz ) {
                cout<<_x<<' '<<_y<<' '<<_z<<' '<<_zz<<'\n';
            }
inline bool CI ( int &_x ) {
    return scanf ( "%d",&_x ) ==1;
}
inline bool CI ( int &_x, int &_y ) {
    return CI ( _x ) &&CI ( _y ) ;
}
inline bool CI ( int &_x, int &_y, int &_z ) {
    return CI ( _x ) &&CI ( _y ) &&CI ( _z ) ;
}
inline bool CI ( int &_x, int &_y, int &_z, int _zz ) {
    return CI ( _x ) &&CI ( _y ) &&CI ( _z ) &&CI ( _zz ) ;
}


const int mov[8][2]= { {-2,+1},{-2,-1},{+2,+1},{+2,-1}, {-1,-2},{+1,-2},{-1,+2},{+1,+2} };
const int rr[]= {-1,+1,+0,+0, -1,-1,+1,+1};
const int cc[]= {+0,+0,-1,+1, -1,+1,+1,-1};
// kate: indent-mode cstyle; indent-width 4; replace-tabs on; 
